import random
import math


def euclidean_distance(point1, point2):
    distance = 0
    for i in range(len(point1)):
        distance += (point1[i] - point2[i]) ** 2
    return math.sqrt(distance)


def assign_cluster(x, c):
    assignments = []
    for point in x:
        # 计算该点到所有聚类中心的距离
        distances = []
        for center in c:
            dist = euclidean_distance(point, center)
            distances.append(dist)

        # 找到最小距离对应的聚类索引
        min_distance = min(distances)
        cluster_index = distances.index(min_distance)
        assignments.append(cluster_index)

    return assignments


def update_centers(data, assignments, k):
    dimensions = len(data[0])
    new_centers = []

    for i in range(k):
        # 找到属于第i个聚类的所有点
        cluster_points = []
        for j in range(len(data)):
            if assignments[j] == i:
                cluster_points.append(data[j])

        # 计算该聚类的中心（均值）
        if len(cluster_points) > 0:
            center = []
            for dim in range(dimensions):
                mean = sum(point[dim] for point in cluster_points) / len(cluster_points)
                center.append(mean)
            new_centers.append(center)
        else:
            # 如果某个聚类没有点，随机选择一个数据点作为中心
            new_centers.append(data[random.randint(0, len(data) - 1)][:])

    return new_centers


def centers_changed(old_centers, new_centers, epsilon):
    for i in range(len(old_centers)):
        distance = euclidean_distance(old_centers[i], new_centers[i])
        if distance > epsilon:
            return True
    return False


def Kmeans(data, k, epsilon, iteration):
    # 1. 随机初始化k个聚类中心
    # 从数据中随机选择k个点作为初始中心
    centers = random.sample(data, k)
    # 深拷贝避免修改原数据
    centers = [center[:] for center in centers]

    iterations_used = 0

    # 2. 迭代优化
    for iter_count in range(iteration):
        iterations_used += 1

        # 2.1 分配每个点到最近的聚类中心
        assignments = assign_cluster(data, centers)

        # 2.2 更新聚类中心
        new_centers = update_centers(data, assignments, k)

        # 2.3 检查收敛条件
        if not centers_changed(centers, new_centers, epsilon):
            print(f"收敛于第 {iterations_used} 次迭代")
            centers = new_centers
            break

        centers = new_centers

    # 最终分配
    final_assignments = assign_cluster(data, centers)

    return centers, final_assignments, iterations_used


# 示例使用
if __name__ == "__main__":
    # 生成一些测试数据
    data = [
        [1.0, 2.0], [1.5, 1.8], [1.2, 2.1],  # 聚类1
        [5.0, 5.0], [5.5, 5.2], [5.1, 4.9],  # 聚类2
        [9.0, 1.0], [9.2, 1.1], [8.8, 1.2]  # 聚类3
    ]
    k = 3
    epsilon = 0.01
    max_iteration = 100

    # 执行K均值聚类
    centers, assignments, iters = Kmeans(data, k, epsilon, max_iteration)
    print(f"\n最终聚类中心:")
    for i, center in enumerate(centers):
        print(f"中心 {i}: {center}")
    print(f"\n数据点分配:")
    for i, (point, cluster) in enumerate(zip(data, assignments)):
        print(f"点 {point} -> 聚类 {cluster}")
    print(f"\n总迭代次数: {iters}")
